POI2013 Take-out

POI2013 Take-out

题目大意：

有n块砖，其中白色是黑色的k倍，求一个消除序列，满足以下条件：

每次消除k+1个块，其中k块白色，一块黑色，并且这k+1块砖从开始到结束中间不能路过已经消除过的块。

$PS.$ 想法题啊。完全没有什么知识点

题解：

我们把序列中的白色看成1，黑色看成-k。这样的话可以求一个前缀和，最近的两项前缀和相同的id，差一定为k+1。

于是我们利用一个栈，按顺序把前缀和推进去，每当新进来的元素和之前栈中某一元素权值相同，就把新来的元素连同两元素之间的元素全部弹出，作为一次操作。

接着，我们倒序输出操作即可。

Code：

#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000001;
int n,k,sum[N],tmp[N];
char str[N];
struct node{
	int id,val;
};
int allc;
struct Stack{
	node num[N];
	int tp;
	Stack(){
		tp=0;
	}
	bool empty(){
		return tp==0;
	}
	void push(node v){
		num[tp++]=v;
	}
	void pop(){
		tp--;
	}
	node top(){
		return num[tp-1];
	}
}stk;
vector<int>ans[N];
bool used[N];
int main(){
	scanf("%d%d%s",&n,&k,str+1);
	for(int i=1;i<=n;i++){
		if(str[i]=='b')sum[i]=sum[i-1]+1;
		else sum[i]=sum[i-1]-k;
		tmp[i]=sum[i];
	}
	sort(tmp+1,tmp+1+n);
	int len=unique(tmp+1,tmp+1+n)-tmp-1;
	for(int i=0;i<=n;i++)sum[i]=lower_bound(tmp+1,tmp+1+len,sum[i])-tmp-1;
	for(int i=0;i<=n;i++){
		if(used[sum[i]]){
			ans[++allc].push_back(i);
			while(stk.top().val!=sum[i]){
				used[stk.top().val]=false;
				ans[allc].push_back(stk.top().id),stk.pop();
			}
		}else{
			stk.push((node){i,sum[i]});
			used[sum[i]]=true;
		}
	}
	for(int i=allc;i>=1;i--){
		for(int j=ans[i].size()-1;j>=0;j--){
			printf("%d ",ans[i][j]);
		}puts("");
	}
	return 0;
}